--[[
--树

	前序遍历 根节点->左子树->右子树
	中序遍历 左子树->根节点->右
	后序遍历 左->右->根
]]

--require "luaext"

local Node = {}
function Node.new(...)
	local instance = setmetatable({}, {__index=Node})
	instance:ctor(...)
	return instance
end
function Node:ctor(data)
	self.left = nil
	self.right = nil
	self.data = data	
end
function Node:setLeft(node)
	self.left = node
end
function Node:getLeft()
	return self.left
end
function Node:setRight(node)
	self.right = node
end
function Node:getRight()
	return self.right
end
function Node:getData()
	return self.data
end

print("____________1")
local QTree = {}
function QTree.new(...)
	local instance = setmetatable({}, {__index=QTree})
	instance:ctor(...)
	return instance
end
function QTree:ctor(tbData)
	self.tbData = tbData
	self.root_node = nil
print("____",tbData)
	--tb 数据转为一个树
	for k, v in pairs(tbData) do 
		local node = Node.new(v)
		if not self.root_node then 
			self.root_node = node 
		else
			local des = self:getEmptyNode(self.root_node)
			if des:getLeft()==nil then 
				des:setLeft(node)
			else
				des:setRight(node)
			end
		end
	end
end

function QTree:getEmptyNode(root) 
	local left_node = root
	local left_deep = 0
	while left_node:getLeft() do 
		left_node = left_node:getLeft()
		left_deep = left_deep + 1
	end
	local right_node = root 
	local right_deep = 0
	while right_node:getRight() do 
		right_node = right_node:getRight()
		right_deep = right_deep + 1
	end
	if right_deep > left_deep then 
		return left_node
	end
	return right_node
end

--取树的深度
function QTree:getDeep()
	local left_node = self.root_node
	local left_deep = 1
	while left_node:getLeft() do 
		left_node = left_node:getLeft()
		left_deep = left_deep + 1
	end
	local right_node = self.root_node 
	local right_deep = 1
	while right_node:getRight() do 
		right_node = right_node:getRight()
		right_deep = right_deep + 1
	end
	if right_deep > left_deep then 
		return right_deep
	end	
	return left_deep
end


function QTree:print()
	local deep = self:getDeep()
	local str_space = " "
	local function printData(node)
		if not node then
			return 
		end
		local str = ""
		for i=1, deep do 
			str = str..str_space
		end
		deep = deep - 1
		print(str..node:getData())
		print(str.."/\\")
		local right_node = node:getRight()
		if right_node then
			print(str_space..right_node:getData())
		end		
		printData(node:getLeft())
		-- printData(node:getRight())

	end

	printData(self.root_node)
end



local tb = {1,2,3,4}

local trre = QTree.new(tb)
trre:print()

print("____tree_deep_",trre:getDeep())